/*
 * Deque.java
 *
 * Created on 2008/08/23 +0900
 *
 * $Revision: 60 $
 * $Date: 2008-12-28 19:27:48 +0000 (Sun, 28 Dec 2008) $
 */

package org.gikolet.framework.util;

import java.util.Enumeration;
import java.util.NoSuchElementException;

/**
 * @author tetsutaro (latest modification by $Author: tetsutaro.ss $)
 * @version $Revision: 60 $ $Date: 2008-12-28 19:27:48 +0000 (Sun, 28 Dec 2008) $
 */
public class Deque implements Queue, Stack {
    public static final int DEFAULT_CAPACITY = 4;

    private Object[] elements;
    private int tail;
    private int head;
    private int count;

    public Deque() {
	this(Deque.DEFAULT_CAPACITY);
    }

    public Deque(int capacity) {
	this.elements = new Object[capacity];

	this.tail = 0;
	this.head = 0;
	this.count = 0;
    }

    /**
     * @see org.gikolet.framework.util.Queue#elements()
     * @see org.gikolet.framework.util.Stack#elements()
     */
    public Enumeration elements() {
	return new Enumeration() {
	    private int index = 0;

	    /**
	     * @see java.util.Enumeration#hasMoreElements()
	     */
	    public boolean hasMoreElements() {
		return this.index < getSize();
	    }

	    /**
	     * @see java.util.Enumeration#nextElement()
	     */
	    public Object nextElement() {
		if (!hasMoreElements()) {
		    throw new NoSuchElementException();
		}
		return element(this.index++);
	    }
	};
    }

    public Object element(int index) {
	if (index >= this.count) {
	    throw new IndexOutOfBoundsException("index[" + index + "] >= size["
		    + this.count + "]");
	}

	return this.elements[(this.head + index) % this.elements.length];
    }

    /**
     * @see org.gikolet.framework.util.Queue#getSize()
     * @see org.gikolet.framework.util.Stack#getSize()
     */
    public int getSize() {
	return this.count;
    }

    /**
     * @see org.gikolet.framework.util.Queue#isEmpty()
     * @see org.gikolet.framework.util.Stack#isEmpty()
     */
    public boolean isEmpty() {
	return this.count == 0;
    }

    public Object peekFirst() {
	if (this.count == 0) {
	    return null;
	}
	return this.elements[this.head];
    }

    public Object peekLast() {
	if (this.count == 0) {
	    return null;
	}
	return this.elements[(this.tail - 1) % this.elements.length];
    }

    private void extendElements() {
	int elementLength = this.elements.length;
	int r = elementLength - this.head;
	long newCapacity = elementLength * 2;

	if (newCapacity > Integer.MAX_VALUE) {
	    throw new IllegalStateException("Deque is large.");
	}

	Object[] newElements = new Object[(int) newCapacity];
	System.arraycopy(this.elements, this.head, newElements, 0, r);
	System.arraycopy(this.elements, 0, newElements, r, this.head);

	this.elements = newElements;
	this.head = 0;
	this.tail = elementLength;
	this.count = elementLength;
    }

    public void pushFirst(Object element) {
	Assert.isNotNull(element);

	if (--this.head < 0) {
	    this.head = this.elements.length - 1;
	}
	this.elements[this.head] = element;
	this.count++;

	if (this.head == this.tail) {
	    extendElements();
	}
    }

    public void pushLast(Object element) {
	Assert.isNotNull(element);

	this.elements[this.tail] = element;
	this.count++;
	if (++this.tail > this.elements.length - 1) {
	    this.tail = 0;
	}

	if (this.tail == this.head) {
	    extendElements();
	}
    }

    public Object popFirst() {
	Object resultElement = this.elements[this.head];
	if (resultElement == null) {
	    return null;
	}

	this.elements[this.head] = null;
	this.count--;
	if (++this.head > this.elements.length - 1) {
	    this.head = 0;
	}

	return resultElement;
    }

    public Object popLast() {
	int tmpTail = this.tail;
	if (--tmpTail < 0) {
	    tmpTail = this.elements.length - 1;
	}

	Object resultElement = this.elements[tmpTail];
	if (resultElement == null) {
	    return null;
	}

	this.elements[this.tail] = null;
	this.count--;
	this.tail = tmpTail;

	return resultElement;
    }

    /**
     * @see org.gikolet.framework.util.Stack#peekStack()
     */
    public Object peekStack() {
	return peekFirst();
    }

    /**
     * @see org.gikolet.framework.util.Stack#popStack()
     */
    public Object popStack() {
	return popFirst();
    }

    /**
     * @see org.gikolet.framework.util.Stack#pushStack(java.lang.Object)
     */
    public void pushStack(Object element) {
	pushFirst(element);
    }

    /**
     * @see org.gikolet.framework.util.Queue#peekQueue()
     */
    public Object peekQueue() {
	return peekFirst();
    }

    /**
     * @see org.gikolet.framework.util.Queue#popQueue()
     */
    public Object popQueue() {
	return popFirst();
    }

    /**
     * @see org.gikolet.framework.util.Queue#pushQueue(java.lang.Object)
     */
    public void pushQueue(Object element) {
	pushLast(element);
    }
}
